\setcounter{listing}{0}
\chapter{二叉树的应用}
\section{实验目的}
\begin{itemize}
    \item 通过本次实验进一步加深对二叉树、线索二叉树、哈夫曼树的基本概念及其操作的理解。
    \item 在此基础上实现二叉树的线索化及编写求二叉树某一结点前驱、后继的操作。
    \item 实现构造哈夫曼树的相关操作（需要使用链式存储表示二叉树）。
\end{itemize}

\section{基础实验题目}
\begin{itemize}
    \item 二叉树的线索化
    \item 构造哈夫曼树结构，并实现对应算法
    \begin{itemize}
        \item 编码
        \item 译码
    \end{itemize}
\end{itemize}

\subsection{二叉树的线索化}
\label{sec:threadBinTree}

在实验四的基础上，修改相关的数据结构和操作，对一个已经生成的二叉树进行线索化（先根次序线索化二叉树、对称序线索化二叉树、后跟次序线索化二叉树),并在线索化二叉树的基础上实现求某一结点的前驱、后继操作。

如有必要，请修改 print 函数用于显示线索化后二叉树相关结点所保存的信息。

\captionof{listing}{线索化、返回前驱和返回后继操作接口的声明}
\label{lstthreadBinTree}
\begin{minted}[linenos, frame=single]{c}
void thread(PLNBinTree t);
PBinTreeNode preNode(PLNBinTree t, PBinTreeNode p);
PBinTreeNode postNode(PLNBinTree t, PBinTreeNode p);
\end{minted}

\subsection{哈夫曼树的实现}
\label{sec:huffmanTree}

根据哈夫曼树的定义，构造其树结构，并实现算法（可参考书上所给出的算法，也可以根据自己的理解写相应的算法）。

\subsubsection{题目一：哈夫曼编码}
有一份电文，文中共使用了 5 个字符 a, b, c, d, e，它们出现的频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（按左子树根结点的权小于等于右子树结点的次序构造），并求出每个字符的哈夫曼编码。\\

得到的哈夫曼树和哈夫曼编码如下：\\

首先需要构造一棵哈夫曼树，然后根据汉服蛮熟对每个字符进行编码。\\

\captionof{listing}{哈夫曼树数据结构定义}
\label{lsthaffmanTree}
\begin{minted}[linenos, frame=single]{c}
typedef char dataType;

typedef struct      //huffman 树结点的结构
{
    int weight;
    dataType data;
    int lchild,rchild,parent;
}huffmanTreeNode;

struct huffmanTree  //huffman 树结构
{
    int m;          //huffman 树外部结点个数
    int root;
    huffmanTreeNode *ht;
};

typedef struct huffmanTree *PHTree;

typedef struct      //huffman 编码的结构
{
    char *bits;     //详细的编码
    int cnt;        //记录这个字符数由几位 bit 表示的
    dataType data;  //编码要表示的字母
}codeType;

typedef struct
{
    codeType *codeList;
    int m;          //huffman 树外部结点个数,也就是编码的个数
}huffmanCodes;

\end{minted}

\subsubsection{题目二：译码}
给出一段二进制代码的电文，要求根据前面实验题目中构造的哈夫曼树进行译码。例如 1011010 这段电文，要求能自动翻译为 bed。

